package com.majie.leetcode.链表;

import com.majie.leetcode.ListNode;

/**
 * https://leetcode-cn.com/problems/middle-of-the-linked-list/
 */
public class _876_链表的中间结点 {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(6);
        ListNode listNode2 = new ListNode(2);
        listNode1.next = listNode2;
        ListNode listNode3 = new ListNode(6);
        listNode2.next = listNode3;
        ListNode listNode4 = new ListNode(3);
        listNode3.next = listNode4;
        ListNode listNode5 = new ListNode(4);
        listNode4.next = listNode5;

        ListNode listNode6 = new ListNode(5);
        listNode5.next = listNode6;

        ListNode listNode7 = new ListNode(6);
        listNode6.next = listNode7;

        ListNode node = middleNode2(listNode1);

        System.out.println(node.val);

    }

    /**
     * 快慢指针法
     */
    public static ListNode middleNode2(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static ListNode middleNode(ListNode head) {
        ListNode node = head;
        if (node == null) {
            return null;
        }
        int count = 1;
        while (node.next != null) {
            node = node.next;
            count++;
        }
        int i = (count + 1) % 2;
        count = i == 0 ? (count + 1) / 2 : (count + 1) / 2 + 1;

        ListNode temp = head;
        for (int j = 1; j < count; j++) {
            temp = temp.next;
        }
        return temp;
    }

}
